﻿#pragma once
#include<iostream>
using namespace std;

//enum Colour
//{
//	red,
//	black
//};
//
//template<class K, class V>
//struct RBTreeNode
//{
//	// 这⾥更新控制平衡也要加⼊parent指针
//	pair<K, V> _kv;
//	RBTreeNode<K, V>* _left;
//	RBTreeNode<K, V>* _right;
//	RBTreeNode<K, V>* _parent;
//	Colour _col;
//	RBTreeNode(const pair<K, V>& kv)
//		:_kv(kv)
//		,_left(nullptr)
//		,_right(nullptr)
//		,_parent(nullptr)
//		,_col(red)
//	{}
//
//};
//
//template<class K, class V>
//class RBTree
//{
//private:
//	using Node = RBTreeNode<K, V>;
//public:
//	RBTree(const pair<K, V>& kv)
//	{
//		_root = new Node(kv);
//	}
//	RBTree() = default;
//
//	//插入
//	bool Insert(const pair<K, V>& data)
//	{
//		if (_root == nullptr)
//		{
//			_root = new Node(data);
//			_root->_col = black;
//			return true;
//		}
//
//		//正常插入
//		Node* cur = _root;
//		Node* cur_parent = nullptr;
//		while (cur != nullptr)
//		{
//			if (data.first > cur->_kv.first)
//			{
//				cur_parent = cur;
//				cur = cur->_right;
//			}
//			else if (data.first < cur->_kv.first)
//			{
//				cur_parent = cur;
//				cur = cur->_left;
//			}
//			else
//				return false;
//		}
//		if (data.first < cur_parent->_kv.first)
//		{
//			cur_parent->_left = new Node(data);
//			cur = cur_parent->_left;
//			cur->_parent = cur_parent;
//		}
//		else
//		{
//			cur_parent->_right = new Node(data);
//			cur = cur_parent->_right;
//			cur->_parent = cur_parent;
//		}
//
//		//当父节点为红的情况
//		if (cur_parent->_col == red)
//		{
//			while (cur_parent && cur_parent->_col != black)
//			{
//				//调整父、叔、爷结点
//				Node* cur_grandfather = cur_parent->_parent;
//				Node* cur_uncle = cur_grandfather->_left;
//				if (cur_parent == cur_uncle)
//					cur_uncle = cur_grandfather->_right;
//
//				//叔结点存在且为红
//				if (cur_uncle && cur_uncle->_col == red)
//				{
//					cur_grandfather->_col = red;
//					cur_parent->_col = cur_uncle->_col = black;
//				}
//
//				//叔结点不存在或存在为黑
//				else
//				{
//					if (cur_grandfather->_left == cur_parent)
//					{
//						if (cur_parent->_left == cur)
//						{
//							RotateR(cur_grandfather);
//							cur_parent->_col = black;
//							cur_grandfather->_col = red;
//						}
//						else
//						{
//							RotateL(cur_parent);
//							RotateR(cur_grandfather);
//							cur->_col = black;
//							cur_grandfather->_col = red;
//						}
//
//					}
//					else
//					{
//						if (cur_parent->_right == cur)
//						{
//							RotateL(cur_grandfather);
//							cur_parent->_col = black;
//							cur_grandfather->_col = red;
//						}
//						else
//						{
//							RotateR(cur_parent);
//							RotateL(cur_grandfather);
//							cur->_col = black;
//							cur_grandfather->_col = red;
//						}
//					}
//				}
//
//				cur = cur_grandfather;
//				cur_parent = cur->_parent;
//			}
//			_root->_col = black;	
//		}
//		return true;
//	}
//		//右旋
//	void RotateR(Node* head)
//	{
//		Node* head_parent = head->_parent;
//		Node* head_left = head->_left;
//		Node* head_left_right = head->_left->_right;
//
//		head->_left = head_left_right;
//		if(head_left_right)                                
//			head_left_right->_parent = head;
//
//		head_left->_right = head;
//		head->_parent = head_left;
//
//		if (head_parent)      
//		{
//			head_left->_parent = head_parent;
//			if (head_left->_kv.first < head_parent->_kv.first)
//				head_parent->_left = head_left;
//			else
//				head_parent->_right = head_left;
//		}
//		else
//		{
//			_root = head_left;
//			_root->_parent = nullptr;
//		}
//
//	}
//
//	//左旋
//	void RotateL(Node* head)
//	{
//		Node* head_parent = head->_parent;
//		Node* head_right = head->_right;
//		Node* head_right_left = head->_right->_left;
//
//		head->_right = head_right_left;
//		if (head_right_left)
//			head_right_left->_parent = head;
//
//		head_right->_left = head;
//		head->_parent = head_right;
//
//		if (head_parent)
//		{
//			head_right->_parent = head_parent;
//			if (head_right->_kv.first < head_parent->_kv.first)
//				head_parent->_left = head_right;
//			else
//				head_parent->_right = head_right;
//		}
//		else
//		{
//			_root = head_right;
//			_root->_parent = nullptr;
//		}
//	}
//		
//	//查找
//	Node* Find(const K& key)
//	{
//		Node* cur = _root;
//		while (cur != nullptr)
//		{
//			if (key < cur->_kv.first)
//				cur = cur->_left;
//			else if (key > cur->_kv.first)
//				cur = cur->_right;
//			else
//				return cur;
//		}
//		return nullptr;
//	}
//
//	int Size()
//	{
//		return _Size(_root);
//	}
//
//	int Height()
//	{
//		return _Height(_root);
//	}
//
//	//中序遍历
//	void InOrder()
//	{
//		_InOrder(_root);
//		cout << endl;
//	}
//
//	//判断是否为红黑树
//	bool IsRBTree()
//	{
//		if(_root->_col == black)
//			return IsRBTree_(_root);
//		return false;
//	}
//
//private:
//	int _Size(Node* root)
//	{
//		if (root == nullptr)
//			return 0;
//
//		int left_size = _Size(root->_left);
//		int right_size = _Size(root->_right);
//		
//		return left_size + right_size + 1;
//	}
//
//	int _Height(Node* root)
//	{
//		if (root == nullptr)
//			return 0;
//
//		int left_height = _Height(root->_left);
//		int right_height = _Height(root->_right);
//
//		return left_height > right_height ? left_height + 1 : right_height + 1;
//	}
//
//	void _InOrder(Node* root)
//	{
//		if (root == nullptr)
//			return;
//
//		_InOrder(root->_left);
//		cout << root->_kv.first << ":" << root->_kv.second << " ";
//		_InOrder(root->_right);
//	}
//
//	bool condition3(Node* root)
//	{
//		if (root == nullptr)
//			return true;
//
//		if (root->_col == red)
//		{
//			if (root->_parent && root->_parent->_col == red)
//				return false;
//		}
//		if (condition3(root->_left))
//		{
//			if (condition3(root->_right))
//				return true;
//		}
//		return false;
//	}
//	bool _IsRBTree(Node* root, int black_record, int& record)
//	{
//		if (root == nullptr)
//		{
//			if (black_record == record)
//				return true;
//			else
//				return false;
//		}
//
//		if (root->_col == black)
//			++black_record;
//		if (_IsRBTree(root->_left, black_record, record))
//		{
//			if (_IsRBTree(root->_right, black_record, record))
//				return true;
//		}
//		return false;
//	}
//	bool IsRBTree_(Node* root)
//	{
//		if (condition3(root))
//		{
//			int record = 0;
//			Node* cur = root;
//			while (cur != nullptr)
//			{
//				if (cur->_col == black)
//					++record;
//				cur = cur->_left;
//			}
//			return _IsRBTree(root, 0, record);
//		}
//		return false;
//	}
//
//	Node* _root = nullptr;
//};








namespace gy
{
	enum Colour
	{
		red,
		black
	};

	template<class T>
	struct RBTreeNode
	{
		// 这⾥更新控制平衡也要加⼊parent指针
		T _data;
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent;
		Colour _col;
		RBTreeNode(const T& data)
			: _data(data)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(red)
		{}

	};

	template<class T, class Ref, class Ptr>
	struct RBTreeInterator
	{
		typedef RBTreeNode<T> Node;
		typedef RBTreeInterator<T, Ref, Ptr> Self;

		RBTreeInterator(Node* node, Node* root)
			:_node(node)
			,_root(root)
		{}
	

		/*Self& operator++()
		{
			if (_node->_left)
			{
				Node* cur = _node->_left;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				return cur;
			}
			else if (_node->_right)
			{
				Node* cur = _node->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				return cur;
			}
			else
			{
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = cur->_parent;
				}
				return parent;
			}
		}*/

		Self operator++()
		{
			if (_node->_right)
			{
				Node* cur = _node->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				_node =  cur;
			}
			else
			{
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = cur->_parent;
				}
				_node =  parent;
			}
			return *this;
		}

		//Self operator++()
		//{
		//	if (_node->_right)
		//	{
		//		// 右不为空，中序下一个访问的节点是右子树的最左(最小)节点
		//		Node* min = _node->_right;
		//		while (min->_left)
		//		{
		//			min = min->_left;
		//		}

		//		_node = min;
		//	}
		//	else
		//	{
		//		// 右为空，祖先里面孩子是父亲左的那个祖先
		//		Node* cur = _node;
		//		Node* parent = cur->_parent;
		//		while (parent && cur == parent->_right)
		//		{
		//			cur = parent;
		//			parent = cur->_parent;
		//		}

		//		_node = parent;
		//	}

		//	return *this;
		//}

		Self operator--()
		{
			if (this->_node == nullptr)
			{
				Node* cur = _root;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_node = cur;
				return *this;
			}
			if (_node->_left)
			{
				Node* cur = _node->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				//不行哦
				//return Self(cur);
				//首先是引用返回，不能返回局部对象
				//传值返回也不行,传值返回并没有改变外面的迭代器it自身，需要it == --it来接收

				_node = cur;
			}
			else
			{
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && cur == parent->_left)
				{
					cur = parent;
					parent = parent->_parent;
				}

				//return Self(parent);
				_node = parent;
			}
			return *this;
		}
	

		

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}

		Node* _node;
		Node* _root;
	};


	template<class K, class T, class KeyOfT, class Compare = less<K>>
	class RBTree
	{
	private:
		typedef RBTreeNode<T> Node;
	public:
		typedef RBTreeInterator<T, T&, T*> Iterator;
		typedef RBTreeInterator<T, const T&, const T*> ConstIterator;

	public:
		/*RBTree(const T& data)
		{
			_root = new Node(data);
		}
		RBTree() = default;*/

		Iterator Begin()
		{
			Node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return { cur, _root };
		}

		ConstIterator Begin() const
		{
			Node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return { cur, _root };
		}

		Iterator End()
		{
			return { nullptr, _root };
		}

		ConstIterator End() const
		{
			return { nullptr, _root };
		}

		//插入
		pair<Iterator, bool> Insert(const T& data)
		{
			if (_root == nullptr)
			{
				_root = new Node(data);
				_root->_col = black;
				return { {_root, _root},true };
			}

			//正常插入
			Node* cur = _root;
			Node* cur_parent = nullptr;
			while (cur != nullptr)
			{
				if (_com(KeyOfT()(cur->_data), KeyOfT()(data)))
				{
					cur_parent = cur;
					cur = cur->_right;
				}
				else if (_com(KeyOfT()(data), KeyOfT()(cur->_data)))
				{
					cur_parent = cur;
					cur = cur->_left;
				}
				else
					return { {cur, _root}, false };
			}
			if (_com(KeyOfT()(data), KeyOfT()(cur_parent->_data)))
			{
				cur_parent->_left = new Node(data);
				cur = cur_parent->_left;
			}
			else
			{
				cur_parent->_right = new Node(data);
				cur = cur_parent->_right;
			}
			cur->_parent = cur_parent;
			Node* ret = cur;

			//当父节点为红的情况
			if (cur_parent->_col == red)
			{
				while (cur_parent && cur_parent->_col != black)
				{
					//调整父、叔、爷结点
					Node* cur_grandfather = cur_parent->_parent;
					Node* cur_uncle = cur_grandfather->_left;
					if (cur_parent == cur_uncle)
						cur_uncle = cur_grandfather->_right;

					//叔结点存在且为红
					if (cur_uncle && cur_uncle->_col == red)
					{
						cur_grandfather->_col = red;
						cur_parent->_col = cur_uncle->_col = black;
					}

					//叔结点不存在或存在为黑
					else
					{
						if (cur_grandfather->_left == cur_parent)
						{
							if (cur_parent->_left == cur)
							{
								RotateR(cur_grandfather);
								cur_parent->_col = black;
								cur_grandfather->_col = red;
							}
							else
							{
								RotateL(cur_parent);
								RotateR(cur_grandfather);
								cur->_col = black;
								cur_grandfather->_col = red;
							}

						}
						else
						{
							if (cur_parent->_right == cur)
							{
								RotateL(cur_grandfather);
								cur_parent->_col = black;
								cur_grandfather->_col = red;
							}
							else
							{
								RotateR(cur_parent);
								RotateL(cur_grandfather);
								cur->_col = black;
								cur_grandfather->_col = red;
							}
						}
					}

					cur = cur_grandfather;
					cur_parent = cur->_parent;
				}
				_root->_col = black;
			}
			return { {ret, _root}, true };
		}
		//右旋
		void RotateR(Node* head)
		{
			Node* head_parent = head->_parent;
			Node* head_left = head->_left;
			Node* head_left_right = head->_left->_right;

			head->_left = head_left_right;
			if (head_left_right)
				head_left_right->_parent = head;

			head_left->_right = head;
			head->_parent = head_left;

			if (head_parent)
			{
				head_left->_parent = head_parent;
				if (_com(KeyOfT()(head_left->_data), KeyOfT()(head_parent->_data)))
					head_parent->_left = head_left;
				else
					head_parent->_right = head_left;
			}
			else
			{
				_root = head_left;
				_root->_parent = nullptr;
			}
		}

		//左旋
		void RotateL(Node* head)
		{
			Node* head_parent = head->_parent;
			Node* head_right = head->_right;
			Node* head_right_left = head->_right->_left;

			head->_right = head_right_left;
			if (head_right_left)
				head_right_left->_parent = head;

			head_right->_left = head;
			head->_parent = head_right;

			if (head_parent)
			{
				head_right->_parent = head_parent;
				if (_com(KeyOfT()(head_right->_data), KeyOfT()(head_parent->_data)))
					head_parent->_left = head_right;
				else
					head_parent->_right = head_right;
			}
			else
			{
				_root = head_right;
				_root->_parent = nullptr;
			}
		}

		//查找
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur != nullptr)
			{
				if (_com(key, KeyOfT()(cur->_data)))
					cur = cur->_left;
				else if (_com(KeyOfT()(cur->_data), key))
					cur = cur->_right;
				else
					return cur;
			}
			return nullptr;
		}

		int Size()
		{
			return _Size(_root);
		}

		int Height()
		{
			return _Height(_root);
		}

		//中序遍历
	/*	void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}*/

		////判断是否为红黑树
		//bool IsRBTree()
		//{
		//	if (_root->_col == black)
		//		return IsRBTree_(_root);
		//	return false;
		//}

	private:
		Node* _root = nullptr;
		Compare _com;

		int _Size(Node* root)
		{
			if (root == nullptr)
				return 0;

			int left_size = _Size(root->_left);
			int right_size = _Size(root->_right);

			return left_size + right_size + 1;
		}

		int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;

			int left_height = _Height(root->_left);
			int right_height = _Height(root->_right);

			return left_height > right_height ? left_height + 1 : right_height + 1;
		}
		

		//void _InOrder(Node* root)
		//{
		//	if (root == nullptr)
		//		return;

		//	_InOrder(root->_left);
		//	cout << KeyOfT()(root->_data) /*<< ":" << root->_kv.second*/ << " ";
		//	_InOrder(root->_right);
		//}

		/*bool condition3(Node* root)
		{
			if (root == nullptr)
				return true;

			if (root->_col == red)
			{
				if (root->_parent && root->_parent->_col == red)
					return false;
			}
			if (condition3(root->_left))
			{
				if (condition3(root->_right))
					return true;
			}
			return false;
		}
		bool _IsRBTree(Node* root, int black_record, int& record)
		{
			if (root == nullptr)
			{
				if (black_record == record)
					return true;
				else
					return false;
			}

			if (root->_col == black)
				++black_record;
			if (_IsRBTree(root->_left, black_record, record))
			{
				if (_IsRBTree(root->_right, black_record, record))
					return true;
			}
			return false;
		}
		bool IsRBTree_(Node* root)
		{
			if (condition3(root))
			{
				int record = 0;
				Node* cur = root;
				while (cur != nullptr)
				{
					if (cur->_col == black)
						++record;
					cur = cur->_left;
				}
				return _IsRBTree(root, 0, record);
			}
			return false;
		}*/

	};

}

